1. Field of the Invention
The present invention relates to digital communication systems. More particularly, the invention relates to decision decoding of received digital information for use in subsequent decoding processes.
2. Background of the Related Art
The process of transmitting digital information may in one sense be thought of as a four-step process as shown in FIG. 1. First, an incoming data stream of electrical digital signals x(t) is coded by a coder 10 to produce coded information C(x(t)) that is provided to a transmitter 20 which transmits the coded information C(x(t)) over a communication medium 30. The coder 10 processes the data stream x(t) so that the coded information C(x(t)) is robust to errors; that is, errors in the coded information C(x(t)) can be detected and corrected. This is necessary because, as will be seen, the transmission process introduces a noise component into the transmitted signal which would corrupt the signal and render it useless were it impossible to be removed.
In an exemplary case, the incoming data x(t) is digitized audio such as voice or music from a known source; the coding unit 10 applies a coding transformation to the incoming data x(t) to produce the coded information C(x(t)); and the transmitter 20 modulates a radio-frequency signal with the coded data C(x(t)) to send it as a radio-frequency signal through the atmosphere which serves as the communication medium 30.
In traversing the communication medium 30, the transmitted information C(x(t)) acquires a noise component n(t), and the resultant signal xxe2x80x2(t)=C(x(t))+n(t) received by a receiver 40 is decoded by a decoding unit 50 to recover the original data stream.
In the above example, the receiver 40 demodulates the received radio frequency signal to produce the received coded information C(x(t))+n(t). The received coded information is error-checked and decoded by the decoding unit 50 to produce the outgoing digital data stream which might then be converted to an analog signal to be amplified for driving a speaker.
It is common in systems such as the one described above for the coder 10 to code C(x(t)) using a convolutional coding system. In contrast to a block code where a block of bits is coded according to a rule defined by the code without regard to previous inputs to the coder, a convolutional code additionally makes use of previous bits it processed in the coding process; thus, the coder 10 is a type of finite state machine.
An example of a convolutional coder of a type which might be used in the coder 10 is shown in FIG. 2A. As is evident from the coder block diagram, coding in this unit depends not only on the state of the current input bit xn but also on the state of the two previous input bits held in the two latches D. Consequently, the coder is a four-state machine as shown by its state diagram in FIG. 2B. From the state diagram it is relatively straightforward to derive the coder""s trellis diagram as shown in FIG. 2C. Here, the branch to a particular state corresponding to a zero input is represented by a solid arrow, and the branch a particular state corresponding to a one input is represented by a dotted arrow.
With the trellis diagram of FIG. 2C, the coding process will be readily apparent to those skilled in the art. Applying an input vector of, e.g., X=(1 1 0 1 0 1 1) produces outputs from the coder of FIG. 2A as shown in TABLE I (assuming the coder starts from an all-zero state).
Thus, for the coder of FIG. 2A, C(X)=(1 1 1 0 1 0 0 0 0 1 0 0 1 0 1 0 1 1).
If the communication medium 30 were error-free and the receiver 40 were assured of providing C(X) to the decoder 50, it could recover the original data stream simply by applying C(X) to the trellis network of the coder state machine and track the path therethrough which generated the sequence C(X). For example, C(X)=(1 1 1 1 0 1 0 0 0 0 1 0 0 1 0 1 0 1 1) wound be generated by the path shown in FIG. 3, where states occupied by the coder are shaded and branches taken by the coder are in bold, with the corresponding coder output C(X) given above each stage. From this, the original input sequence X=(1 1 0 1 0 1 1) can be obtained.
The above discussion and those hereinafter assume that the coder 10 and decoder 50 operate according to the same coding algorithm; that is, they both base their processing on the same coder circuit, state machine and the like; thus, dimensions of the trellis network necessary to accurately represent the coding algorithm are known to the decoder, the number of stages necessary in the trellis network is known, etc. Further, for the purposes of explanation only it is assumed that in this example the coder state machine begins in an all-zero state (this is not a requirement of real-world systems), and that the input stream X is padded with a sufficient number of zeroes to return it to such a state at the conclusion of the coding/decoding process.
Assume now that the signal received and processed by the receiver 40 has a non-zero noise component. This might result in the decoding unit 50 receiving Cxe2x80x2(X)=(1 1 1 0 1 1 0 0 0 1 1 0 1 0 1 0 1 1), with the sixth and eleventh bits being errors due to n(t). In this case, the original input sequence cannot be found simply by applying Cxe2x80x2(X) to the trellis of FIG. 2C. A typical error-correction algorithm used in this situation is the Viterbi error correction algorithm described as follows.
1. Given the trellis network, associate a metric with each stage in the trellis and set the metrics for all states in the first stage to zero.
2. For each state in the next stage, find the xe2x80x9cdistancexe2x80x9d of each branch to it from the next-received subsequence of Cxe2x80x2(X) and add it to the metric of the current state from which it branches.
3. Choose the minimum of the values calculated in Step 2 as the metric for the given stage in the next stage, and choose the branch leading to it as the survivor branch to that state.
4. Repeat Steps 2 and 3 until the end of the trellis network is reached.
5. Select the state in the last stage of the trellis network having the minimum metric and work backwards to the beginning by selecting survivor paths to produce the best guess about C(X).
If the coder is known to start from an all-zero state, the system is preferably designed so that traceback is always done to the all-zero state in the first stage. This can be done by, for example, initializing the all-zero state to zero and initializing the other states to large values.
Also, there are various techniques available to determine the state from which to begin a traceback. For example, at the end of a frame when the coder ends in a known state (in the example, 00), start the traceback from that known state.
Application of the Viterbi decoding algorithm to the corrupted stream Cxe2x80x2(X) and the trellis network of FIG. 2C is shown in FIG. 4. Here,
the metric for a state is shown at its center;
the distance of a current subsequence from a given branch is shown by a number above the branch;
survivor branches (except for those in the best guess path) have a white arrowhead; and
the best guess path is in bold.
First, metrics of all states in the initial stage are set to zero. Then, the distance (here, the Hamming distance) between the subsequence 11 and each branch value is assigned to that branch. For the first node, the two branches are 00 and 11, so they receive values of 2 and 0. The next node has branches 01 and 10, so each of these branches receives a metric of 1. The third node has branches 11 and 00, so they respectively receive values of 0 and 2. Finally, the fourth node has branches 10 and 01 which each receive a Hamming distance of 1.
Then, for the first state in the second stage, the two branch values to it are 2 and 0, so its metric is set at 0 and the 0 branch from the third state in the previous stage is set as its survivor branch. For the second state in the second stage, the two branch values are 0 and 2, so its metric is set at 0 and the 0 branch from the first stage in the first stage is set as its survivor branch. Next, the third state in the second stage receives values of 1 and 1, so its metric is set to 1 and one side is randomly or deterministically set as the survivor branch. Finally, the last state in the second stage receives values of 1 and 1, so it has a metric of 1 and one branch is chosen as the survivor branch.
This process is repeated to the end of the trellis as shown in FIG. 4. Then, starting at the first node in the last stage (since it has the lowest metric of the last stage), survivor paths are traced back to the first stage. As can be seen from FIG. 4, the result is the same path travelled in the error-free case. Thus, the Viterbi algorithm has successfully eliminated the error contribution of n(t).
Although the Viterbi algorithm works well for situations such as those given above, it is not always practical to directly implement the algorithm in this way. For example, some communication systems make use of alternative information-carrying techniques such as quadrature amplitude modulation (QAM), which requires alternative methods of retrieving the received data stream.
Additionally, some communication systems make use of techniques which restrict the type of decoding systems that can be used therein. For example, soft decision decoding cannot be used with interleaved systems such as IEEE 802.11a and other OFDM systems because each bit was transmitted as part of a different constellation.
In view of the above deficiencies of the prior art, it is an object of the present invention to provide a digital information decoding system which can be used in a wide variety of communication systems.
It is another object of the present invention to provide a digital information decoding system that can be used with a wide variety of information demodulation techniques.
It is a further object of the present invention to provide a digital information decoding system that can be used with interleaving digital communication systems.
The above objects are achieved according to a first aspect of the present invention by providing a Viterbi decoding system which interprets bits in received QAM constellations as many-valued parameters rather than binary valued parameters. It performs the Viterbi algorithm using these many-valued parameters to provide results superior to hard decision decoding. Rather than applying a hard 0-1 function to the QAM data, the system uses a non-stepped linear or curved transfer function to assign values to the bits.